맨위로가기

탐욕 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하여 문제를 해결하는 알고리즘 설계 패러다임이다. 이 알고리즘은 일반적으로 단순하고 구현하기 쉽지만, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 대해서만 최적의 해를 보장한다. 탐욕 알고리즘은 동적 계획법과 달리, 한 번 선택한 것을 재고려하지 않는 특징을 가지며, 다익스트라 알고리즘, 프림 알고리즘, 크루스칼 알고리즘 등에서 사용된다. 하지만 외판원 문제와 같은 경우에는 최적의 해를 찾지 못하며, 네트워크 라우팅, 활동 선택 문제 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

  • 조합 알고리즘 - 피셔-예이츠 셔플
    피셔-예이츠 셔플은 유한 집합에서 임의의 순열을 생성하는 알고리즘으로, 피셔와 예이츠가 처음 소개한 후 더스텐펠트에 의해 컴퓨터에 최적화되었으며, 구현 시 편향 요인을 주의해야 한다.
  • 조합 알고리즘 - 게일-섀플리 알고리즘
    게일-섀플리 알고리즘은 두 그룹 간의 안정적인 매칭을 찾아내는 알고리즘으로, 각 참가자의 선호도를 기반으로 안정적인 매칭을 생성하며 제안하는 측에 최적의 결과를 제공하고, 2012년 노벨 경제학상을 수상했다.
  • 최적화 알고리즘 및 방법 - 신뢰 영역
    신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
  • 최적화 알고리즘 및 방법 - 확률적 계획법
    확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법을 포함하며, 생물학, 경제, 금융 공학 등 여러 분야에 응용된다.
  • 매트로이드 이론 - 매트로이드 마이너
    매트로이드 마이너는 매트로이드에서 부분집합 제거 또는 제한 연산을 반복하여 얻어지는 매트로이드로, 매트로이드의 성질 보존, 구조 분석, 그래프 이론과의 연결, 여러 종류의 매트로이드, 구조 파악 및 복잡성 분석, 효율적인 테스트 알고리즘 개발 등에 활용된다.
  • 매트로이드 이론 - 안둘레
    안둘레는 그래프 이론에서 가장 짧은 사이클의 길이를 나타내며, 사이클이 없는 그래프는 무한대의 안둘레를 갖고, 그래프의 연결도, 접합 크기, 밖둘레와 관련되어 그래프 채색과 확장성 분석, 그리고 케이지 연구에 활용된다.
탐욕 알고리즘

2. 정의 및 특징

탐욕 알고리즘은 매 순간 최적이라고 생각되는 선택을 하는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다. 모든 문제에서 최적해를 보장하지는 않는다.

탐욕 알고리즘은 지역 탐색법과 함께 근사 알고리즘의 기본적인 방법 중 하나이다. 문제를 여러 부분 문제로 나누어 각각 독립적으로 평가하고, 평가값이 높은 순서대로 선택하여 해를 구한다. 동적 계획법과 달리 항상 하나의 상태만 유지하며, 한 번 선택한 요소는 다시 고려하지 않는다. 따라서 최적해를 보장할 수는 없지만, 부분 문제 해결과 단순한 정렬만으로 구현할 수 있으며, 많은 문제에서 다항 시간 안에 근사해를 구할 수 있다.

조합 최적화 문제에서 탐욕 알고리즘은 특히 유용하다. 문제에 따라서는 최적해를 얻거나, 최소한의 정밀도 보장(근사도)을 계산할 수 있다.

탐욕 알고리즘을 기본 전략으로 사용하면서도 최적해를 구할 수 있다는 것이 증명된 알고리즘은 다음과 같다.



최적화 문제에서 최적해가 되기 위해서는 동적 계획법과 같이 부분 구조 최적성(optimal substructure영어)을 만족해야 한다. 즉, 부분 문제를 해결하고 이를 이용하여 전체 문제의 최적해를 구할 수 있어야 한다.

2. 1. 탐욕 선택 속성

탐욕 선택 속성은 주어진 시점에서 최선으로 보이는 선택을 하고, 재귀적으로 나머지 하위 문제를 해결하는 것을 의미한다.[2] 탐욕 알고리즘의 선택은 이전 선택에 영향을 받지만, 미래 선택이나 하위 문제의 해에는 의존하지 않는다. 탐욕 알고리즘은 각 단계에서 탐욕적 선택을 반복하여 문제를 더 작은 문제로 축소한다. 즉, 선택을 재고하지 않는다. 이는 동적 계획법과의 주요 차이점인데, 동적 계획법은 완전 탐색을 통해 해를 보장하며, 이전 단계 결정을 고려하여 경로를 재고할 수 있다.

2. 2. 최적 부분 구조

"어떤 문제의 최적해가 그 부분 문제의 최적해를 포함하면, 그 문제는 최적 부분 구조를 가진다고 한다."[2]

3. 유형

탐욕 알고리즘은 '근시안적'이며 '비가역적'인 특징을 보인다.[4] '최적 부분 구조'를 가진 문제에만 이상적이지만, 많은 간단한 문제에 대해 가장 적합한 알고리즘이다. 탐욕 알고리즘은 검색 또는 분기 한정 알고리즘 내에서 옵션의 우선 순위를 정하는 선택 알고리즘으로 사용될 수도 있다.[4]

탐욕 알고리즘의 몇 가지 변형은 다음과 같다.[4]


  • 순수 탐욕 알고리즘
  • 직교 탐욕 알고리즘
  • 완화된 탐욕 알고리즘


탐욕법은 지역 탐색법과 함께 근사 알고리즘의 가장 기본적인 사고방식 중 하나이다.

이 알고리즘은 문제의 요소를 여러 부분 문제로 분할하여 각각 독립적으로 평가를 수행하고, 평가값이 높은 순서대로 선택해 나감으로써 해를 얻는다. 동적 계획법과 달리 유지하는 상태는 항상 하나이며, 한 번 선택한 요소를 다시 고려하지 않는다. 따라서 얻어지는 해가 최적해라는 보장은 없지만, 부분 문제의 해법과 단순한 정렬만으로 프로그램을 구현할 수 있으며, 많은 문제에 대해 다항 시간 내에 근사 알고리즘이 된다.

문제를 여러 개로 분할하는 방법은 특히 조합 최적화 문제와 잘 맞는다. 문제에 따라서는 엄밀해(최적해)를 얻을 수 있거나, 최소한의 정밀도 보장(근사도)을 산출할 수 있는 것도 있다. 이 때문에 현재에도 종종 이 문제의 연구에 사용되고 있다.

4. 한계 및 실패 사례

탐욕 알고리즘은 지역 탐색법과 함께 근사 알고리즘의 가장 기본적인 사고방식 중 하나이다.

이 알고리즘은 문제의 요소를 여러 부분 문제로 분할하여 각각 독립적으로 평가를 수행하고, 평가값이 높은 순서대로 선택해 나감으로써 해를 얻는 방법이다. 동적 계획법과 달리 유지하는 상태는 항상 하나이며, 한 번 선택한 요소를 다시 고려하는 일은 없다. 이 때문에 얻어지는 해가 최적해라는 보장은 없지만, 부분 문제의 해법과 단순한 정렬만으로 프로그램을 구현할 수 있으며, 많은 문제에 대해 다항 시간 내에 근사 알고리즘이 된다.

문제를 여러 개로 분할하는 방법은 특히 조합 최적화 문제와 궁합이 좋다. 문제에 따라서는 엄밀해(최적해)를 얻을 수 있거나, 최소한의 정밀도 보장(근사도)을 산출할 수 있는 것도 있다. 이 때문에 현재에도 종종 이 문제의 연구에 사용되고 있다.

4. 1. 실패 사례

가장 큰 합에 도달하기 위해, 탐욕 알고리즘은 각 단계에서 최적의 즉각적인 선택으로 보이는 것을 선택하므로, 두 번째 단계에서 3 대신 12를 선택하고 99를 포함하는 최상의 해에 도달하지 못합니다.


탐욕 알고리즘은 다른 많은 문제에 대해 최적의 해를 생성하지 못하며, 심지어 ''유일한 최악의 가능성''을 만들어낼 수도 있다. 한 예로 위에 언급된 외판원 문제가 있다. 도시 개수 별로, 최인접 이웃 휴리스틱이 유일한 최악의 가능한 경로를 생성하는 도시 간의 거리 할당이 있다.[3] 다른 가능한 예시는 지평선 효과를 참조하라.

다음은 배낭 문제에 대한 적용 예시이다. 이 문제의 경우, 각 짐을 분할하여 평가함으로써 적용할 수 있다.

# 배낭 문제의 각 짐에 대한 평가값을 결정한다. (가치) ÷ (부피)라는 숫자가 자주 사용된다.

# 평가값이 가장 높은 짐을 선택한다.

# 해당 짐을 배낭에 넣어도 최대 용량을 초과하지 않으면 배낭에 넣는다.

# 모든 짐을 평가값 순서대로 선택하고 위 작업을 반복한다.

이 문제에 관해서는 탐욕법으로는 최적해를 얻을 수 없다.

5. 이론적 배경

탐욕 알고리즘은 조합 최적화 및 이론 컴퓨터 과학 분야에서 오랫동안 연구되어 왔다. 탐욕적 휴리스틱은 많은 문제에서 최적의 결과를 생성하지 못하는 것으로 알려져 있다.[5] 따라서 다음과 같은 질문들이 제기된다.


  • 어떤 문제에 대해 탐욕 알고리즘이 최적으로 작동하는가?
  • 어떤 문제에 대해 탐욕 알고리즘이 대략적인 최적 해를 보장하는가?
  • 어떤 문제에 대해 탐욕 알고리즘이 ''절대'' 최적 해를 생성하지 못하는가?


집합 커버와 같은 특정 문제뿐만 아니라, 매트로이드와 같은 일반적인 문제 유형에 대한 이러한 질문에 답하는 많은 문헌들이 존재한다.

5. 1. 매트로이드

매트로이드는 벡터 공간의 선형 독립 개념을 임의의 집합으로 일반화한 수학적 구조이다. 최적화 문제에 매트로이드 구조가 있다면, 적절한 탐욕 알고리즘을 통해 최적해를 구할 수 있다.[6]

5. 2. 서브모듈 함수

집합 \Omega의 부분 집합에 정의된 함수 f가 모든 S, T \subseteq \Omega에 대해 f(S)+f(T)\geq f(S\cup T)+f(S\cap T)를 만족하면 서브모듈(submodular)이라고 한다.

함수 f를 최대화하는 집합 S를 찾는다고 가정해 보자. 각 단계에서 f를 가장 많이 증가시키는 요소를 점진적으로 추가하여 집합 S를 구축하는 탐욕 알고리즘은 출력으로 최소한 (1 - 1/e) \max_{X \subseteq \Omega} f(X)인 집합을 생성한다.[7] 즉, 탐욕 알고리즘은 최적 솔루션의 (1 - 1/e) \approx 0.63 배의 상수 계수 내에서 성능을 발휘한다.

출력에 기수 제약과 같은 추가적인 제약이 가해질 때 유사한 보장이 증명될 수 있지만,[8] 종종 탐욕 알고리즘의 약간의 변형이 필요하다.[9]

6. 응용 분야

탐욕 알고리즘은 다양한 분야에서 응용된다. 주요 응용 분야는 다음과 같다:


  • 활동 선택 문제: 서로 충돌하지 않는 최대 수의 활동을 선택하는 문제이다.[4]
  • 크리스탈 퀘스트: 외판원 문제와 유사하게 크리스탈을 수집하는 매킨토시 컴퓨터 게임이다. 데모 모드에서 게임은 탐욕 알고리즘을 사용하지만, 인공 지능이 장애물을 고려하지 않아 빨리 끝나는 경우가 많다.[5]
  • 매칭 퍼슈트: 신호 근사에 적용된 탐욕 알고리즘의 한 예이다.[6]
  • Malfatti 문제: 주어진 삼각형 안에 총 면적이 최대가 되는 세 개의 서로 겹치지 않는 원을 찾는 문제에 대한 최적해를 찾는다.[7]
  • 허프만 코딩: 최적해를 찾는 허프만 트리를 구성하는 데 사용된다.[8]
  • 의사 결정 트리 학습: 일반적으로 사용되지만 최적해를 보장하지는 않는다. ID3 알고리즘이 그 예시 중 하나이다.[9]
  • A* 탐색 알고리즘: 그래프 탐색 및 최단 경로 찾기에 대한 검증 가능한 최적의 탐욕 알고리즘이다. A* 탐색은 경로 비용을 과대 평가하지 않는 "허용 가능한 휴리스틱"이 필요하다.[10]
  • 시쿼터 및 렘펠-지브-웰치 알고리즘: 문법 유도를 위한 탐욕 알고리즘이다.


탐욕법은 지역 탐색법과 함께 근사 알고리즘의 가장 기본적인 사고방식 중 하나이다. 탐욕 알고리즘은 문제의 요소를 여러 부분 문제로 분할하여 각각 독립적으로 평가를 수행하고, 평가값이 높은 순서대로 선택하여 해를 얻는다. 동적 계획법과 달리 유지하는 상태는 항상 하나이며, 한 번 선택한 요소를 다시 고려하지 않는다. 따라서 얻어지는 해가 최적해라는 보장은 없지만, 부분 문제의 해법과 단순한 정렬만으로 구현할 수 있으며, 많은 문제에 대해 다항 시간 내에 근사 알고리즘이 된다.

문제 분할 방법은 특히 조합 최적화 문제와 잘 맞는다. 문제에 따라서는 엄밀해(최적해)를 얻을 수 있거나, 최소한의 정밀도 보장(근사도)을 산출할 수 있는 경우도 있어 연구에 자주 사용된다.

6. 1. 최적 해를 보장하는 알고리즘

탐욕 알고리즘은 모든 데이터를 소모적으로 처리하지 않기 때문에, 일반적으로 전역적으로 최적의 해를 찾지 못하는 경우가 많다. 탐욕 알고리즘은 특정 선택에 너무 일찍 몰두하여 나중에 최적의 전체 해를 찾는 것을 방해할 수 있다. 예를 들어, 그래프 채색 문제에 대한 모든 알려진 탐욕적 채색 알고리즘과 다른 모든 NP-완전 문제는 일관적으로 최적의 해를 찾지 못한다. 그럼에도 불구하고, 탐욕 알고리즘은 빠르게 생각해낼 수 있고 종종 최적의 해에 대한 좋은 근사치를 제공하기 때문에 유용하다.

탐욕 알고리즘이 주어진 문제 클래스에 대해 전역 최적해를 산출한다는 것이 증명될 수 있다면, 동적 계획법과 같은 다른 최적화 방법보다 빠르기 때문에 일반적으로 선택되는 방법이 된다. 이러한 탐욕 알고리즘의 예로는 최소 신장 트리를 찾는 크루스칼 알고리즘과 프림 알고리즘, 그리고 최적의 허프만 트리를 찾는 알고리즘 등이 있다.

몇몇 알고리즘은 탐욕법을 기본 전략으로 하면서도, 엄밀해(최적해)를 구할 수 있는 것으로 증명되었다.

최적화 문제에서 엄밀해가 되기 위해서는, 동적 계획법과 마찬가지로 부분 구조 최적성(optimal substructure|옵티멀 서브스트럭쳐영어)을 가져야 한다. 즉, 부분 문제를 풀고 그것을 이용하여 최적화 문제의 엄밀해를 풀 수 있어야 한다.

6. 2. 네트워크 라우팅

탐욕 알고리즘은 네트워크 라우팅에서도 나타난다. 탐욕적 라우팅을 사용하면, 메시지는 목적지에 "가장 가까운" 인접 노드로 전달된다. 노드의 위치 (따라서 "가까움")의 개념은 애드 혹 네트워크에서 사용되는 지리적 라우팅과 같이 물리적 위치에 의해 결정될 수 있다. 위치는 또한 스몰 월드 라우팅 및 분산 해시 테이블과 같은 완전히 인공적인 구조일 수도 있다.

6. 3. 기타 응용

탐욕 알고리즘은 모든 데이터를 충분히 고려하지 않기 때문에 종종 최적의 해를 찾지 못한다. 특정 선택에 너무 빨리 집중하여 나중에 최적의 해를 찾는 것을 방해할 수 있다. 예를 들어, 그래프 채색 문제나 다른 NP-완전 문제에 대한 탐욕적 알고리즘은 항상 최적의 해를 찾는 것은 아니다.[1] 그러나 탐욕 알고리즘은 빠르게 결과를 도출하고, 종종 최적의 해에 가까운 근사치를 제공하기 때문에 유용하다.[1]

만약 탐욕 알고리즘이 특정 문제에 대해 항상 최적의 해를 찾는다는 것이 증명된다면, 이는 동적 계획법과 같은 다른 방법보다 빠르기 때문에 일반적으로 선호되는 방법이 된다.[2] 이러한 예로는 최소 신장 트리를 찾는 크루스칼 알고리즘과 프림 알고리즘, 그리고 최적의 허프만 트리를 찾는 알고리즘이 있다.[2]

탐욕 알고리즘은 네트워크 라우팅에도 사용된다. 탐욕적 라우팅은 메시지를 목적지에 "가장 가까운" 이웃 노드로 전달하는 방식이다.[3] 노드의 위치는 지리적 라우팅처럼 물리적 위치일 수도 있고, 스몰 월드 라우팅이나 분산 해시 테이블처럼 인공적인 구조일 수도 있다.[3]

그 외 응용 사례는 다음과 같다:

  • 활동 선택 문제: 서로 겹치지 않는 최대 개수의 활동을 선택하는 문제이다.[4]
  • 크리스탈 퀘스트: 외판원 문제와 비슷하게 크리스탈을 수집하는 매킨토시 컴퓨터 게임이다. 게임의 데모 모드에서는 탐욕 알고리즘을 사용하여 크리스탈을 수집하지만, 장애물을 고려하지 않아 종종 빨리 끝난다.[5]
  • 매칭 퍼슈트: 신호 근사에 사용되는 탐욕 알고리즘의 일종이다.[6]
  • Malfatti 문제: 주어진 삼각형 안에 총 면적이 최대가 되는 세 개의 서로 겹치지 않는 원을 찾는 문제에 대한 최적의 해를 찾는다.[7]
  • 허프만 코딩: 최적의 해를 찾는 허프만 트리를 구성하는 데 사용된다.[8]
  • 의사 결정 트리 학습: 일반적으로 사용되지만, 최적의 해를 보장하지는 않는다. ID3 알고리즘이 그 예시 중 하나이다.[9]
  • 다익스트라 알고리즘과 A* 탐색 알고리즘: 그래프 탐색 및 최단 경로 찾기에 대한 검증 가능한 최적의 탐욕 알고리즘이다. A* 탐색은 경로 비용을 과대평가하지 않는 "허용 가능한 휴리스틱"이 필요하다.[10]
  • 크루스칼 알고리즘과 프림 알고리즘: 주어진 연결된 그래프의 최소 신장 트리를 구성하는 탐욕 알고리즘으로, 일반적으로 항상 최적의 해를 찾는다.
  • 시쿼터 및 렘펠-지브-웰치 알고리즘: 문법 유도를 위한 탐욕 알고리즘이다.

7. 한국 사회와 탐욕 알고리즘

(내용 없음)

참조

[1] 웹사이트 greedy algorithm http://xlinux.nist.g[...] U.S. National Institute of Standards and Technology 2012-08-17
[2] 서적
[3] 논문 Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
[4] 간행물 Some remarks on greedy algorithms https://doi.org/10.1[...] 1996-12-01
[5] 서적
[6] 서적
[7] 서적
[8] 서적
[9] 서적
[10] 웹사이트 Lecture 5: Introduction to Approximation Algorithms http://www.win.tue.n[...] TU Eindhoven


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com